﻿//#pragma once
//#include <string>
//
////状态标识，防止元素删除后对查找后面冲突值的影响
//enum State
//{
//	EXIST,
//	EMPTY,
//	DELETE
//};
//
////存放的元素
//template<class K, class V>
//struct HashData
//{
//	pair<K, V> _kv;
//	State _state = EMPTY;
//};
//
////哈希函数
//template<class K>
//struct HashFunc
//{
//	size_t operator()(const K& key)
//	{
//		return size_t(key);
//	}
//};
//
////string做哈希表的key很常见，对哈希函数进行string特化
//template<>
//struct HashFunc<string>
//{
//	// 字符串转换成整形，可以把字符asci码相加即可
//	// 但是直接相加的话，类似"abcd"和"bcad"这样的字符串计算出是相同的
//	// 这⾥⽤上次的计算结果去乘以⼀个质数去解决，这个质数⼀般取
//	// 31, 131等效果会⽐较好
//	size_t operator()(const string& s)
//	{
//		size_t hash = 0;
//		for (auto ch : s)
//		{
//			hash += ch;
//			hash *= 131;
//		}
//		return hash;
//	}
//};
//
////找比n大，离n最近的质数
//inline unsigned long __stl_next_prime(unsigned long n)
//{
//	// Note: assumes long is at least 32 bits.
//	static const int __stl_num_primes = 28;
//	static const unsigned long __stl_prime_list[__stl_num_primes] = {
//		53, 97, 193, 389, 769,
//		1543, 3079, 6151, 12289, 24593,
//		49157, 98317, 196613, 393241, 786433,
//		1572869, 3145739, 6291469, 12582917, 25165843,
//		50331653, 100663319, 201326611, 402653189, 805306457,
//		1610612741, 3221225473, 4294967291
//	};
//	const unsigned long* first = __stl_prime_list;
//	const unsigned long* last = __stl_prime_list + __stl_num_primes;
//	//在first和last找大于等于n位置的指针
//	const unsigned long* pos = lower_bound(first, last, n);
//	return pos == last ? *(last - 1) : *pos;
//}
//
//namespace open_address
//{
//	template<class K, class V, class Hash = HashFunc<K>>
//	class HashTable
//	{
//	public:
//		HashTable()
//			:_tables(__stl_next_prime(0))
//			, _n(0)
//		{
//		}
//
//
//		void CheckCapacity()
//		{
//			//当负载因子>=0.7时，扩容
//			if (_n * 10 / _tables.size() >= 7)
//			{
//				//方法一：旧表映射到新表
//				/*vector<HashData<K, V>> newtables(_tables.size() * 2);
//				for (auto& data : _tables)
//				{
//					if (data._state == EXIST)
//					{
//						size_t newhashi = HashFunc(data._kv.first) % newtables.size();
//						newtables[newhashi]._kv = data._kv;
//						newtables[newhashi]._state = EXIST;
//					}
//				}
//
//				_tables.swap(newtables);*/
//
//				//方法二：利用新哈希表
//				HashTable<K, V> newht;
//				//newht._tables.resize(_tables.size() * 2);
//				newht._tables.resize(__stl_next_prime(_tables.size() + 1));
//
//				for (auto& data : _tables)
//				{
//					if (data._state == EXIST)
//					{
//						newht.Insert(data._kv);
//					}
//				}
//
//				_tables.swap(newht._tables);
//			}
//		}
//
//		bool Insert(const pair<K, V>& kv)
//		{
//			//如果找到了重复元素，直接返回false
//			if (Find(kv.first))
//				return false;
//
//			//检查负载因子是否需要扩容
//			CheckCapacity();
//
//			//哈希函数
//			Hash hashfunc;
//			size_t hashi = hashfunc(kv.first) % _tables.size();
//
//			//线性探测
//			while (_tables[hashi]._state == EXIST)
//			{
//				++hashi;
//				hashi %= _tables.size();
//			}
//
//			_tables[hashi]._kv = kv;
//			_tables[hashi]._state = EXIST;
//			++_n;
//
//			return true;
//		}
//
//		HashData<K, V>* Find(const K& key)
//		{
//			Hash hashfunc;
//			size_t hashi = hashfunc(key) % _tables.size();
//
//			while (_tables[hashi]._state != EMPTY)
//			{
//				if (_tables[hashi]._state == EXIST
//					&& _tables[hashi]._kv.first == key)
//				{
//					return &_tables[hashi];
//				}
//
//				hashi++;
//				hashi %= _tables.size();
//			}
//
//			return nullptr;
//
//		}
//
//		bool Erase(const K& key)
//		{
//			HashData<K, V>* ret = Find(key);
//			if (ret)
//			{
//				ret->_state = DELETE;
//				return true;
//			}
//			else
//			{
//				return false;
//			}
//
//		}
//
//	private:
//		vector<HashData<K, V>> _tables;
//		size_t _n;
//	};
//
//
//}
//
//namespace hash_bucket
//{
//	//哈希表里存节点的指针
//	template<class K, class V>
//	struct HashNode
//	{
//		pair<K, V> _kv;
//		HashNode<K, V>* _next;
//
//		HashNode(const pair<K, V>& kv)
//			:_kv(kv)
//			, _next(nullptr)
//		{
//		}
//	};
//
//	template<class K, class V, class hash = HashFunc<K>>
//	class HashTable
//	{
//		typedef HashNode<K, V> Node;
//	public:
//		HashTable()
//			: _tables(__stl_next_prime(0))
//			, _n(0)
//		{
//		}
//
//
//		void CheckCapacity()
//		{
//			//当哈希表里节点的数量与哈希表大小相等时扩容
//			if (_n == _tables.size())
//			{
//				//把哈希桶里的链表每个节点拆下来插入newht效率太低了
//				/*HashTable<K, V> newht;
//				newht._tables.resize(__stl_next_prime(_tables.size() + 1));
//				for (size_t i = 0; i < _tables.size(); ++i)
//				{
//					Node* cur = _tables[i];
//					while (cur)
//					{
//						newht.Insert(cur->_kv);
//						cur = cur->_next;
//					}
//				}
//				_tables.swap(newht._tables);*/
//
//				hash hashfunc;
//				vector<Node*> newtables(__stl_next_prime(_tables.size() + 1));
//				for (size_t i = 0; i < _tables.size(); ++i)
//				{
//					Node* cur = _tables[i];
//					while (cur)
//					{
//						Node* next = cur->_next;
//						size_t hashi = hashfunc(cur->_kv.first) % newtables.size();
//						//头插
//						cur->_next = newtables[hashi];
//						newtables[hashi] = cur;
//
//						cur = next;
//					}
//
//					_tables[i] = nullptr;
//				}
//				_tables.swap(newtables);
//			}
//		}
//
//		bool Insert(const pair<K, V>& kv)
//		{
//			//不允许重复插入
//			if (Find(kv.first))
//				return false;
//
//			//检查扩容
//			CheckCapacity();
//
//			hash hashfunc;
//			size_t hashi = hashfunc(kv.first) % _tables.size();
//
//			//头插
//			Node* newnode = new Node(kv);
//			newnode->_next = _tables[hashi];
//			_tables[hashi] = newnode;
//			++_n;
//
//			return true;
//		}
//
//		Node* Find(const K& key)
//		{
//			hash hashfunc;
//			size_t hashi = hashfunc(key) % _tables.size();
//			Node* cur = _tables[hashi];
//
//			while (cur)
//			{
//				if (cur->_kv.first == key)
//					return cur;
//				cur = cur->_next;
//			}
//
//			return nullptr;
//		}
//
//		bool Erase(const K& key)
//		{
//			hash hashfunc;
//			size_t hashi = hashfunc(key) % _tables.size();
//
//			Node* prev = nullptr;
//			Node* cur = _tables[hashi];
//			while (cur)
//			{
//				if (cur->_kv.first == key)
//				{
//					//头节点的情况特殊处理
//					if (prev == nullptr)
//					{
//						_tables[hashi] = cur->_next;
//					}
//					else
//					{
//						prev->_next = cur->_next;
//					}
//
//					delete cur;
//					--_n;
//					return true;
//				}
//				else
//				{
//					prev = cur;
//					cur = cur->_next;
//				}
//			}
//
//			return false;
//		}
//
//	private:
//		vector<Node*> _tables;
//		size_t _n = 0;
//	};
//
//
//
//}